home *** CD-ROM | disk | FTP | other *** search
/ Enigma Amiga Life 109 / EnigmaAmiga109CD.iso / dalla rivista / host contacted / jikes.lha / jikes-1.11 / src / depend.cpp < prev    next >
C/C++ Source or Header  |  2000-01-07  |  15KB  |  473 lines
  1. // $Id: depend.cpp,v 1.15 2000/01/07 00:25:53 lord Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #include "config.h"
  11. #include <time.h>
  12. #include "control.h"
  13. #include "ast.h"
  14. #include "semantic.h"
  15.  
  16. //
  17. // Note that the types are ordered based on on the subtype relationship. We reverse
  18. // the order here because the desired order for processing is the supertype relationship.
  19. //
  20. inline void TypeCycleChecker::ReverseTypeList()
  21. {
  22.     for (int head = 0, tail = type_list.Length() - 1; head < tail; head++, tail--)
  23.     {
  24.         TypeSymbol *temp = type_list[head];
  25.         type_list[head] = type_list[tail];
  26.         type_list[tail] = temp;
  27.     }
  28.  
  29.     return;
  30. }
  31.  
  32.  
  33. void TypeCycleChecker::PartialOrder(Tuple<Semantic *> &semantic, int start)
  34. {
  35.     type_list.Reset();
  36.  
  37.     //
  38.     // assert that the "index" of all types that should be checked is initially set to OMEGA
  39.     //
  40.     for (int i = start; i < semantic.Length(); i++)
  41.     {
  42.         Semantic *sem = semantic[i];
  43.  
  44.         for (int k = 0; k < sem -> compilation_unit -> NumTypeDeclarations(); k++)
  45.         {
  46.             AstClassDeclaration *class_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> ClassDeclarationCast();
  47.             AstInterfaceDeclaration *interface_declaration = sem -> compilation_unit -> TypeDeclaration(k) -> InterfaceDeclarationCast();
  48.             SemanticEnvironment *env = (class_declaration ? class_declaration -> semantic_environment
  49.                                                           : (interface_declaration ? interface_declaration -> semantic_environment
  50.                                                                                    : (SemanticEnvironment *) NULL));
  51.             if (env) // type was successfully compiled thus far?
  52.             {
  53.                 TypeSymbol *type = env -> Type();
  54.                 if (type -> index == OMEGA)
  55.                    ProcessSubtypes(type);
  56.             }
  57.         }
  58.     }
  59.  
  60.     ReverseTypeList();
  61.  
  62.     return;
  63. }
  64.  
  65.  
  66. void TypeCycleChecker::PartialOrder(SymbolSet &types)
  67. {
  68.     //
  69.     // assert that the "index" of all types that should be checked is initially set to OMEGA
  70.     //
  71.     for (TypeSymbol *type = (TypeSymbol *) types.FirstElement(); type; type = (TypeSymbol *) types.NextElement())
  72.     {
  73.         if (type -> index == OMEGA)
  74.             ProcessSubtypes(type);
  75.     }
  76.  
  77.     ReverseTypeList();
  78.  
  79.     return;
  80. }
  81.  
  82.  
  83. void TypeCycleChecker::ProcessSubtypes(TypeSymbol *type)
  84. {
  85.     stack.Push(type);
  86.     int indx = stack.Size();
  87.     type -> index = indx;
  88.  
  89.     type -> subtypes_closure = new SymbolSet;
  90.     type -> subtypes_closure -> Union(*(type -> subtypes));
  91.     for (TypeSymbol *subtype = (TypeSymbol *) type -> subtypes -> FirstElement();
  92.                      subtype;
  93.                      subtype = (TypeSymbol *) type -> subtypes -> NextElement())
  94.     {
  95.         if (subtype -> index == OMEGA)
  96.              ProcessSubtypes(subtype);
  97.         type -> index = Min(type -> index, subtype -> index);
  98.         type -> subtypes_closure -> Union(*(subtype -> subtypes_closure));
  99.     }
  100.  
  101.     if (type -> index == indx)
  102.     {
  103.         TypeSymbol *scc_subtype;
  104.         do
  105.         {
  106.             scc_subtype = stack.Top();
  107.             scc_subtype -> index = CYCLE_INFINITY;
  108.             *(scc_subtype -> subtypes_closure) = *(type -> subtypes_closure);
  109.             type_list.Next() = scc_subtype;
  110.             stack.Pop();
  111.         } while (scc_subtype != type);
  112.     }
  113.  
  114.     return;
  115. }
  116.  
  117.  
  118. ConstructorCycleChecker::ConstructorCycleChecker(AstClassBody *class_body)
  119. {
  120.     for (int k = 0; k < class_body -> NumConstructors(); k++)
  121.     {
  122.         AstConstructorDeclaration *constructor_declaration = class_body -> Constructor(k);
  123.         if (constructor_declaration -> index == OMEGA)
  124.             CheckConstructorCycles(constructor_declaration);
  125.     }
  126.  
  127.     return;
  128. }
  129.  
  130.  
  131. void ConstructorCycleChecker::CheckConstructorCycles(AstConstructorDeclaration *constructor_declaration)
  132. {
  133.     stack.Push(constructor_declaration);
  134.     int indx = stack.Size();
  135.     constructor_declaration -> index = indx;
  136.  
  137.     AstConstructorDeclaration *called_constructor_declaration = NULL;
  138.  
  139.     AstConstructorBlock *constructor_block = constructor_declaration -> constructor_body;
  140.     if (constructor_block -> explicit_constructor_invocation_opt)
  141.     {
  142.         AstThisCall *this_call = constructor_block -> explicit_constructor_invocation_opt -> ThisCallCast();
  143.         MethodSymbol *called_constructor = (MethodSymbol *) (this_call ? this_call -> symbol : NULL);
  144.  
  145.         if (called_constructor)
  146.         {
  147.             called_constructor_declaration = (AstConstructorDeclaration *) called_constructor -> method_or_constructor_declaration;
  148.  
  149.             if (called_constructor_declaration -> index == OMEGA)
  150.                 CheckConstructorCycles(called_constructor_declaration);
  151.             constructor_declaration -> index = Min(constructor_declaration -> index, called_constructor_declaration -> index);
  152.         }
  153.     }
  154.  
  155.     if (constructor_declaration -> index == indx)
  156.     {
  157.         //
  158.         // If the constructor_declaration is alone in its strongly connected component (SCC),
  159.         // and it does not form a trivial cycle with itsself, pop it, mark it and return;
  160.         //
  161.         if (constructor_declaration == stack.Top() && constructor_declaration != called_constructor_declaration)
  162.         {
  163.             stack.Pop();
  164.             constructor_declaration -> index = CYCLE_INFINITY;
  165.         }
  166.         //
  167.         // Otherwise, all elements in the stack up to (and including) constructor_declaration form an SCC.
  168.         // Pop them off the stack, in turn, mark them and issue the appropriate error message.
  169.         //
  170.         else
  171.         {
  172.             do
  173.             {
  174.                 called_constructor_declaration = stack.Top();
  175.                 stack.Pop();
  176.                 called_constructor_declaration -> index = CYCLE_INFINITY;
  177.  
  178.                 constructor_block = (AstConstructorBlock *) called_constructor_declaration -> constructor_body;
  179.                 AstMethodDeclarator *constructor_declarator = called_constructor_declaration -> constructor_declarator;
  180.  
  181.                 Semantic *sem = called_constructor_declaration -> constructor_symbol
  182.                                                                -> containing_type -> semantic_environment -> sem;
  183.                 sem -> ReportSemError(SemanticError::CIRCULAR_THIS_CALL,
  184.                                        constructor_block -> explicit_constructor_invocation_opt -> LeftToken(),
  185.                                        constructor_block -> explicit_constructor_invocation_opt -> RightToken(),
  186.                                        sem -> lex_stream -> NameString(constructor_declarator -> identifier_token));
  187.             } while (called_constructor_declaration != constructor_declaration);
  188.         }
  189.     }
  190.  
  191.     return;
  192. }
  193.  
  194.  
  195. //
  196. // assert that the "index" of all types that should be checked is initially set to OMEGA
  197. //
  198. void TypeDependenceChecker::PartialOrder()
  199. {
  200.     for (FileSymbol *file_symbol = (FileSymbol *) file_set.FirstElement();
  201.                      file_symbol;
  202.                      file_symbol = (FileSymbol *) file_set.NextElement())
  203.     {
  204.         for (int j = 0; j < file_symbol -> types.Length(); j++)
  205.         {
  206.             TypeSymbol *type = file_symbol -> types[j];
  207.             if (type -> incremental_index == OMEGA)
  208.                 ProcessType(type);
  209.         }
  210.     }
  211.  
  212.     for (int k = 0; k < type_trash_bin.Length(); k++)
  213.     {
  214.         TypeSymbol *type = type_trash_bin[k];
  215.         if (type -> incremental_index == OMEGA)
  216.             ProcessType(type);
  217.     }
  218.  
  219.     return;
  220. }
  221.  
  222.  
  223. void TypeDependenceChecker::ProcessType(TypeSymbol *type)
  224. {
  225.     stack.Push(type);
  226.     int indx = stack.Size();
  227.     type -> incremental_index = indx;
  228.  
  229.     type -> dependents -> RemoveElement(type); // if dependents is reflexive make it non-reflexive - saves time !!!
  230.     type -> dependents_closure = new SymbolSet;
  231.     type -> dependents_closure -> AddElement(type); // compute reflexive transitive closure
  232.     for (TypeSymbol *dependent = (TypeSymbol *) type -> dependents -> FirstElement();
  233.                      dependent;
  234.                      dependent = (TypeSymbol *) type -> dependents -> NextElement())
  235.     {
  236.         if (dependent -> incremental_index == OMEGA)
  237.              ProcessType(dependent);
  238.         type -> incremental_index = Min(type -> incremental_index, dependent -> incremental_index);
  239.         type -> dependents_closure -> Union(*(dependent -> dependents_closure));
  240.     }
  241.  
  242.     if (type -> incremental_index == indx)
  243.     {
  244.         TypeSymbol *scc_dependent;
  245.         do
  246.         {
  247.             scc_dependent = stack.Top();
  248.             scc_dependent -> incremental_index = CYCLE_INFINITY;
  249.             *(scc_dependent -> dependents_closure) = *(type -> dependents_closure);
  250.             type_list.Next() = scc_dependent;
  251.             stack.Pop();
  252.         } while (scc_dependent != type);
  253.     }
  254.  
  255.     return;
  256. }
  257.  
  258.  
  259. void TypeDependenceChecker::OutputMake(FILE *outfile, char *output_name, Tuple<FileSymbol *> &file_list)
  260. {
  261.     assert(outfile);
  262.  
  263.     for (int i = 0; i < file_list.Length(); i++)
  264.     {
  265.         FileSymbol *file_symbol = file_list[i];
  266.         char *name = file_symbol -> FileName();
  267.         int length = file_symbol -> FileNameLength() - (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
  268.                                                                                 : FileSymbol::class_suffix_length);
  269.  
  270.         char *class_name = new char[length + FileSymbol::class_suffix_length + 1],
  271.              *java_name = new char[length + FileSymbol::java_suffix_length + 1];
  272.  
  273.         strncpy(class_name, name, length);
  274.         strcpy(&class_name[length], FileSymbol::class_suffix);
  275.         strncpy(java_name, name, length);
  276.         strcpy(&java_name[length], FileSymbol::java_suffix);
  277.  
  278.         fprintf(outfile, "%s : %s\n", output_name, java_name);
  279.  
  280.         if (i > 0) // Not the first file in the list
  281.         {
  282.             fprintf(outfile, "%s : %s\n", output_name, class_name);
  283.         }
  284.  
  285.         delete [] class_name;
  286.         delete [] java_name;
  287.     }
  288.  
  289.     return;
  290. }
  291.  
  292.  
  293. void TypeDependenceChecker::OutputMake(FileSymbol *file_symbol)
  294. {
  295.     //
  296.     //
  297.     //
  298.     char *name;
  299.     char *buf;
  300.     int length;
  301.  
  302.     if (control -> option.directory == NULL)
  303.     {
  304.         name = file_symbol -> FileName();
  305.         length = file_symbol -> FileNameLength() - (file_symbol -> IsJava() ? FileSymbol::java_suffix_length
  306.                                                                                 : FileSymbol::class_suffix_length);
  307.     }
  308.     else
  309.     {
  310.         name = file_symbol -> Utf8Name();
  311.         length = strlen(name);
  312.  
  313.         DirectorySymbol *dir_symbol = file_symbol -> OutputDirectory();
  314.         char *dir_name = dir_symbol -> DirectoryName();
  315.         int dir_length = strlen(dir_name);
  316.         
  317.         buf = new char[length + FileSymbol::class_suffix_length + dir_length + 2];
  318.         strcpy(buf, dir_name);
  319.  
  320. #ifdef UNIX_FILE_SYSTEM
  321.         buf[dir_length] = (char)U_SLASH;
  322. #elif defined(WIN32_FILE_SYSTEM)
  323.         buf[dir_length] = (char)U_BACKSLASH;
  324. #endif
  325.  
  326.         strcpy(&buf[dir_length+1], name);
  327.         name = buf;
  328.         length = dir_length + 1 + length;
  329.     }
  330.  
  331.  
  332.  
  333.     char *output_name = new char[length + FileSymbol::class_suffix_length + 1],
  334.          *u_name = new char[length + strlen(StringConstant::U8S__DO_u) + 1];
  335.  
  336.     strncpy(output_name, name, length);
  337.     strncpy(u_name, name, length);
  338.     strcpy(&output_name[length], FileSymbol::class_suffix);
  339.     strcpy(&u_name[length], StringConstant::U8S__DO_u);
  340.  
  341.     //
  342.     //
  343.     //
  344.     SymbolSet file_set;
  345.     for (int i = 0; i < file_symbol -> types.Length(); i++)
  346.     {
  347.         TypeSymbol *type = file_symbol -> types[i];
  348.         for (TypeSymbol *parent = (TypeSymbol *) type -> parents_closure -> FirstElement();
  349.                          parent;
  350.                          parent = (TypeSymbol *) type -> parents_closure -> NextElement())
  351.         {
  352.             FileSymbol *symbol = parent -> file_symbol;
  353.             if (symbol && (! symbol -> IsZip()))
  354.                 file_set.AddElement(symbol);
  355.         }
  356.     }
  357.     file_set.RemoveElement(file_symbol);
  358.  
  359.     //
  360.     //
  361.     //
  362.     Tuple<FileSymbol *> file_list(file_set.Size());
  363.     file_list.Next() = file_symbol;
  364.     for (FileSymbol *symbol = (FileSymbol *) file_set.FirstElement(); symbol; symbol = (FileSymbol *) file_set.NextElement())
  365.         file_list.Next() = symbol;
  366.  
  367.     FILE *outfile = ::SystemFopen(u_name, "w");
  368.     if (outfile == NULL)
  369.         Coutput << "*** Cannot open file " << u_name << "\n";
  370.     else
  371.     {
  372.         OutputMake(outfile, output_name, file_list);
  373.         fclose(outfile);
  374.     }
  375.  
  376.     delete [] output_name;
  377.     delete [] u_name;
  378.     if (control -> option.directory)
  379.         delete [] buf;
  380.  
  381.     return;
  382. }
  383.  
  384.  
  385. void TypeDependenceChecker::OutputDependences()
  386. {
  387.     SymbolSet new_file_set;
  388.  
  389.     for (int i = 0; i < type_list.Length(); i++)
  390.     {
  391.         TypeSymbol *type = type_list[i];
  392.         type -> parents_closure = new SymbolSet;
  393.  
  394.         FileSymbol *file_symbol = type -> file_symbol;
  395.         if (file_symbol && (! file_symbol -> IsZip()))
  396.             new_file_set.AddElement(file_symbol);
  397.     }
  398.  
  399.     for (int l = 0; l < type_list.Length(); l++)
  400.     {
  401.         TypeSymbol *parent = type_list[l];
  402.  
  403.         for (TypeSymbol *dependent = (TypeSymbol *) parent -> dependents_closure -> FirstElement();
  404.                          dependent;
  405.                          dependent = (TypeSymbol *) parent -> dependents_closure -> NextElement())
  406.                 dependent -> parents_closure -> AddElement(parent);
  407.     }
  408.  
  409.     for (FileSymbol *symbol = (FileSymbol *) new_file_set.FirstElement(); symbol; symbol = (FileSymbol *) new_file_set.NextElement())
  410.         OutputMake(symbol);
  411.  
  412.     for (int n = 0; n < type_list.Length(); n++)
  413.     {
  414.         TypeSymbol *type = type_list[n];
  415.         delete type -> parents_closure;
  416.         type -> parents_closure = NULL;
  417.     }
  418.  
  419.     return;
  420. }
  421.  
  422.  
  423. void TopologicalSort::Process(TypeSymbol *type)
  424. {
  425.     pending -> AddElement(type);
  426.  
  427.     for (TypeSymbol *super_type = (TypeSymbol *) type -> supertypes_closure -> FirstElement();
  428.                      super_type;
  429.                      super_type = (TypeSymbol *) type -> supertypes_closure -> NextElement())
  430.     {
  431.         if (type_collection.IsElement(super_type))
  432.         {
  433.             if (! pending -> IsElement(super_type))
  434.                 Process(super_type);
  435.         }
  436.     }
  437.  
  438.     type_list.Next() = type;
  439.  
  440.     return;
  441. }
  442.  
  443.  
  444. void TopologicalSort::Sort()
  445. {
  446.     type_list.Reset();
  447.  
  448.     for (TypeSymbol *type = (TypeSymbol *) type_collection.FirstElement(); type; type = (TypeSymbol *) type_collection.NextElement())
  449.     {
  450.         if (! pending -> IsElement(type))
  451.             Process(type);
  452.     }
  453.  
  454.     pending -> SetEmpty();
  455.  
  456.     return;
  457. }
  458.  
  459.  
  460. TopologicalSort::TopologicalSort(SymbolSet &type_collection_, Tuple<TypeSymbol *> &type_list_) : type_collection(type_collection_),
  461.                                                                                                  type_list(type_list_)
  462. {
  463.     pending = new SymbolSet(type_collection.Size());
  464.  
  465.     return;
  466. }
  467.  
  468.  
  469. TopologicalSort::~TopologicalSort()
  470. {
  471.     delete pending;
  472. }
  473.